/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * <p>
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * <p>
 *  
 * <p>
 * 示例:
 * <p>
 * board =
 * [
 * ['A','B','C','E'],
 * ['S','F','C','S'],
 * ['A','D','E','E']
 * ]
 * <p>
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 *  
 * <p>
 * 提示：
 * <p>
 * board 和 word 中只包含大写和小写英文字母。
 * 1 <= board.length <= 200
 * 1 <= board[i].length <= 200
 * 1 <= word.length <= 10^3
 */
class Solution {

    public static void main(String[] args) {
        char[][] matrix = new char[3][4];
        char[] a1 = new char[]{'A', 'B', 'C', 'E'};
        char[] a2 = new char[]{'S', 'F', 'C', 'S'};
        char[] a3 = new char[]{'A', 'D', 'E', 'E'};
        matrix[0] = a1;
        matrix[1] = a2;
        matrix[2] = a3;
        System.out.println(exist(matrix, "ABCCED"));
        System.out.println(exist(matrix, "SEE"));
        //System.out.println(exist(matrix, "ABCB"));
    }

    public static boolean exist(char[][] board, String word) {
        // 遍历这个数组，找到第一个匹配的字母
        int height = board.length;
        int length = board[0].length;
        char[] words = word.toCharArray();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i][j] == words[0]) {
                    if (match(board, words, 1, i, j, height, length)) {
                        return true;
                    }
                }
            }
        }
        // 遍历结束都没有完成返回否
        return false;
    }

    private static boolean match(char[][] board, char[] words, int p, int i, int j, int height, int length) {
        if (p == words.length) {
            return true;
        }
        // 先把当前值置为非字母，防止影响后续判断】
        char tmp = board[i][j];
        board[i][j] = 0;
        // 开始上下左右找路
        if (i > 0 && board[i - 1][j] == words[p]) {
            if (match(board, words, p + 1, i - 1, j, height, length)) {
                return true;
            }
        }
        if (i + 1 < height && board[i + 1][j] == words[p]) {
            if (match(board, words, p + 1, i + 1, j, height, length)) {
                return true;
            }
        }
        if (j > 0 && board[i][j - 1] == words[p]) {
            if (match(board, words, p + 1, i, j - 1, height, length)) {
                return true;
            }
        }
        if (j + 1 < length && board[i][j + 1] == words[p]) {
            if (match(board, words, p + 1, i, j + 1, height, length)) {
                return true;
            }
        }
        board[i][j] = tmp;
        return false;
    }
}